Description

给定一个由 n 个字符串 s 组成的字典，再给定 m 句话 t ，求每句话在该字典下可以理解的最长前缀。
$n\leq 20,m\leq 50,|s|\leq 10,|t|\leq 2\times 10^6$

Solution

Description

给定长度为 n 的字符串 s ，每次只能交换相邻两个位置。求使得 s 为回文串的最小交换次数。无解输出 -1 。
$n\leq 10^6$，保证都是大写字母

Solution

回文自动机（PAM）是针对给定串，包含了该串所有回文子串的信息的自动机。
PAM 的每个节点代表了一个本质不同的回文子串，记 s[p] 为点 p 代表的回文子串。
PAM 的每个节点有三个基础属性：fail/len/child 。
len：a[p].len 表示 s[p] 的长度。

Description

给你一棵 $n$ 个点的树，每个点为黑色或白色。要求维护两个操作：

• 改变点 u 的颜色
阅读全文 »

Description

给定一张图，需要支持两个操作：

• 查询 $u,v$ 两点间的必经边数量。
阅读全文 »

Description

给定一棵 $n$ 个点的树，树上每个点有一个颜色。对于每一种颜色，求有多少无向路径至少经过一次该颜色。
$n\leq 10^5$

Solution

有一个夜晚我烧毁了所有的记忆，从此我的梦就透明了。有一个早晨我扔掉了所有的昨天，从此我的脚步就轻盈了。

Pro A Simple Math

题意：给定 $a,b,c$ ，求 $\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}\sum\limits_{k=1}^{c}i\times j\times k\pmod{998244353}$ 的值。

数据范围：$1\leq a,b,c\leq10^9$

简单的提取公因式可得原式等价于求 $\sum\limits_{i=1}^{a}i\sum\limits_{j=1}^{b}j\sum\limits_{k=1}^{c}k$ 。

Pro A 106

题意：给定 $n$ ，求满足 $3^a+5^b=n$ 的任意一组解。

数据范围：$n\leq 10^{18}$

预处理出值在 $10^{18}$ 次方以内的 $3$ 的幂和 $5$ 的幂然后直接枚举。

在计数问题中我们经常需要对求和的式子进行转化来加速求和。这里略作整理。

基础-组合恒等式

• 阅读全文 »